public class MinPathSum {
    // 矩阵的最小路径和
    // https://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    public int minPathSum (int[][] matrix) {
        // write code here
        // dp[i][j]表示走到(i,j)位置的最小路径和
        // dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + matrix[i-1][j-1]
        int len1 = matrix.length;
        int len2 = matrix[0].length;
        int[][] dp = new int[len1+1][len2+1];
        int INF = 0x3f3f3f3f;
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = INF;
        }
        for (int j = 2; j <= len2; j++) {
            dp[0][j] = INF;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + matrix[i-1][j-1];
            }
        }
        return dp[len1][len2];
    }

    /**
     * 空间优化
     * @param matrix
     * @return
     */
    public int minPathSum1 (int[][] matrix) {
        // write code here
        // 空间优化
        // 使用一维数组来代替二维数组，并且填表的顺序为从上到下、从左到右
        int len1 = matrix.length;
        int len2 = matrix[0].length;
        int[] dp = new int[len2+1];
        int INF = 0x3f3f3f3f;
        for (int j = 2; j <= len2; j++) {
            dp[j] = INF;
        }
        dp[0] = INF;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                dp[j] = Math.min(dp[j], dp[j-1]) + matrix[i-1][j-1];
            }
        }
        return dp[len2];
    }
}
